class Solution
{
public:
    int minFallingPathSum(vector<vector<int>> &matrix)
    {
        int n = matrix.size();
        vector<int> dpLast(n, 0);
        vector<int> dp(n);
        for (int row = 0; row < n; ++row)
        {
            for (int i = 0; i < n; ++i)
            {
                int lastMin = dpLast[i];
                if (i > 0)
                {
                    lastMin = min(lastMin, dpLast[i - 1]);
                }
                if (i < n - 1)
                {
                    lastMin = min(lastMin, dpLast[i + 1]);
                }
                dp[i] = matrix[row][i] + lastMin;
            }
            dpLast.swap(dp);
        }
        return *min_element(dpLast.begin(), dpLast.end());
    }
};